package mht.practice.ListNode;

/**
 * Created by MHT on 2017/9/15.
 */
public class delete {
    /**
     * 给出一单链表头指针head和一节点指针toBeDeleted，O(1)时间复杂度删除节点tBeDeleted
     * 对于删除节点，我们普通的思路就是让该节点的前一个节点指向该节点的下一个节点
     * ，这种情况需要遍历找到该节点的前一个节点，时间复杂度为O(n)。对于链表，
     * 链表中的每个节点结构都是一样的，所以我们可以把该节点的下一个节点的数据复制到该节点
     * ，然后删除下一个节点即可。要注意最后一个节点的情况，这个时候只能用常见的方法来操作，先找到前一个节点，但总体的平均时间复杂度还是O(1)
     */
    public void delete(ListNode head, ListNode toDelete){
        if(toDelete == null){
            return;
        }
        if(toDelete.next != null){          // 要删除的是一个中间节点
            toDelete.val = toDelete.next.val;       // 将下一个节点的数据复制到本节点!
            toDelete.next = toDelete.next.next;
        }
        else{       // 要删除的是最后一个节点！
            if(head == toDelete){       // 链表中只有一个节点的情况
                head = null;
            }else{
                ListNode node = head;
                while(node.next != toDelete){   // 找到倒数第二个节点
                    node = node.next;
                }
                node.next = null;
            }
        }
    }
}
